# 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
#
#  示例 1：
# 输入：head = [1,2,3,4,5]
# 输出：[5,4,3,2,1]
#
#  示例 2：
# 输入：head = [1,2]
# 输出：[2,1]
#
#  示例 3：
# 输入：head = []
# 输出：[]
# Definition for singly-linked list.
from com.example.linked.common import *


class Solution:
    """
        递归方式实现(从最后一个节点开始翻转)
    """

    def reverseList2(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        newHead = self.reverseList2(head.next)  # newHead是每次递归的后一个节点也即是最终反转后的头节点
        head.next.next = head  # head是每次递归的newHead的前一个节点
        head.next = None

        return newHead

    """
        迭代方式实现(从第一个节点开始)
        遍历链表并逐个反转
    """

    def reverseList1(self, head: ListNode) -> ListNode:
        # 写法一
        # pre, tmp, cur = None, head, head
        # while cur:
        #     tmp = tmp.next
        #     cur.next = pre
        #     pre = cur
        #     cur = tmp
        # return pre

        # 写法二
        last = None
        while head:
            # 因为最后需要移动到下一个节点进行遍历，所以临时保存一下 head.next
            nextHead = head.next
            # 这两步完成反转操作
            head.next = last
            last = head
            # 遍历下一个节点
            head = nextHead
        return last

    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverseList1(head)


if __name__ == "__main__":
    l = getListNode(2, 4, 6, 1)
    res = Solution().reverseList(l)
    vistListNode(res)
